package test5;

import java.util.Arrays;
import java.util.Scanner;

public class Solution3 { //Floyd
    public static void main(String[] args) {
        System.out.println("请输入顶点个数：");
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[][] distance = new int[num][num];
        char[] vertexArray = new char[num];
        System.out.println("请输入已知点之间的距离矩阵：");
        int weight;
        for (int i = 0; i < num; i++) { //初始化矩阵
            for (int j = 0; j < num; j++) {
                weight = sc.nextInt();
                if (i == j){ //自己和自己的距离为0
                    distance[i][j] = 0;
                }else if (weight == 0){ //没有连接设为999表示不可达
                    distance[i][j] = 999;
                }else {
                    distance[i][j] = weight;
                }
            }
        }
        for (int i = 0; i < num; i++) {
            vertexArray[i] = (char) (65 + i);
        }
        Graph graph = new Graph(vertexArray,distance);
        graph.Floyd();
        for (int i = 0; i < num; i++) {//打印使用中间点后的距离矩阵
            for (int j = 0; j < num; j++) {
                System.out.print(distance[i][j] + "\t");
            }
            System.out.println();
        }
        graph.showPath();
    }
}

class Graph{
    //图中各个顶点的集合
    private char[] vertexArray;
    //各个顶点作为出发顶点到其他顶点的最短距离的数组
    private int[][] distance;
    //各个顶点的前驱结点，即通过哪个顶点可以到达该顶点
    private int[][] pre;

    public Graph(char[] vertexArray, int[][] distance){
        this.vertexArray = vertexArray;
        this.distance = distance;
        this.pre = new int[this.distance.length][this.distance[0].length];
        //初始化前驱结点
        for (int i = 0; i < this.vertexArray.length; i++) {
            Arrays.fill(pre[i],i); // 例如A->A,A->B，A能到的每一个点都将其前驱结点初始化为A对应的索引i
        }
    }

    public void Floyd(){
        for (int k = 0; k < vertexArray.length; k++) { //中间点
            for (int i = 0; i < vertexArray.length; i++) { //起点
                for (int j = 0; j < vertexArray.length; j++) { //终点
                    if (distance[i][k] + distance[k][j] < distance[i][j]){
                        distance[i][j] = distance[i][k] + distance[k][j]; //更新最短距离
                        pre[i][j] = pre[k][j]; //更新前驱结点
                    }
                }
            }
        }
    }

    public void showPath(){
        int tempIndex;
        String path = "";
        for (int i = 0; i < vertexArray.length; i++) {
            for (int j = 0; j < vertexArray.length; j++) {
                tempIndex = j;
                while (pre[i][tempIndex] != i){ //如果当前点的前驱结点不为自己，继续向前寻找
                    tempIndex = pre[i][tempIndex];
                    path = vertexArray[tempIndex] + "->" + path;// 该循环里的path保存的都是中间结点
                }
                path = vertexArray[i] + "->" + path + vertexArray[j]; //将起点、中间结点、终点进行拼接
                System.out.print(vertexArray[i] + "到" + vertexArray[j] + "的最短距离为" + distance[i][j] + "(" + path + ")" + "\t\t");
                path = "";
            }
            System.out.println();
        }
    }
}
